/*
 * @lc app=leetcode.cn id=218 lang=golang
 *
 * [218] 天际线问题
 */

// @lc code=start

import (
	"container/heap"
	"sort"
)

type node struct {
	right, height int
}
type heaps []node

func (h heaps) Less(i, j int) bool {
	return h[i].height > h[j].height
}

func (h heaps) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}
func (h heaps) Len() int {
	return len(h)
}

func (h *heaps) Push(x interface{}) {
	*h = append(*h, x.(node))
}

func (h *heaps) Pop() interface{} {
	old := *h
	v := old[len(old)-1]
	*h = old[:len(old)-1]
	return v
}

func getSkyline(buildings [][]int) [][]int {
	m := len(buildings)
	n := 2 * m
	tmp := make([]int, 0, n)
	for _, building := range buildings {
		tmp = append(tmp, building[0], building[1])
	}
	sort.Ints(tmp)
	idx := 0
	h := heaps{}
	res := make([][]int, 0, m)
	for _, left := range tmp {
		// 获取小于 left 的所有端点
		for idx < m && buildings[idx][0] <= left {
			heap.Push(&h, node{buildings[idx][1], buildings[idx][2]})
			idx++
		}
		// 右边界小于 left 的所有至高点移除
		for len(h) > 0 && h[0].right <= left {
			heap.Pop(&h)
		}
		// 获取 left 横坐标的最高点
		maxn := 0
		if len(h) > 0 {
			maxn = h[0].height
		}
		// 如果当前 left 的最高点与之前 left 的不同，则添加至结果中
		if len(res) == 0 || maxn != res[len(res)-1][1] {
			res = append(res, []int{left, maxn})
		}
	}
	return res
}

// @lc code=end
